# -*- coding: utf-8 -*-

DishPosMap = {}
PillarStackMap = {}

#0,1,2->A,B,C
PillarA = 0
PillarB = 1
PillarC = 2

PillarCount = 3

def Hanoi(n):
    PillarStackMap = {}
    DishPosMap = {}
    PillarStackMap[PillarA] = []
    PillarStackMap[PillarB] = []
    PillarStackMap[PillarC] = []
    print("-----------------InitDataOver-----------------")
    # print("DishPosMap:",DishPosMap)
    # print("PillarStackMap:",PillarStackMap)

    stack = PillarStackMap[PillarA]
    for x in range(1,n + 1):
        stack.append(x)
        # print("stack:",stack)
        DishPosMap[x] = PillarA
    print("-----------------InitStackOver----------------")
    # print("DishPosMap:",DishPosMap)
    print("PillarStackMap:",PillarStackMap)

    opLst = []
    GenerateBTree(n,opLst)
    print("-----------------GenerateBTreeOver------------")
    # print("opLst:",opLst)

    while len(opLst) > 0:
        dish = opLst.pop(0)
        direc = (dish + n) % 2 != 0

        pillar = DishPosMap[dish]
        nextPillar = GetNextPillar(pillar,direc)

        stackFrom = PillarStackMap[pillar]
        stackTo = PillarStackMap[nextPillar]

        Move(stackFrom,stackTo)
        DishPosMap[dish] = nextPillar

    print("PillarStackMap:",PillarStackMap)

def Move(stackFrom,stackTo):
    dish = stackFrom.pop(0)
    stackTo.insert(0,dish)
    return dish

def GenerateBTree(n,L):
    if(n == 0):
        return
    GenerateBTree(n-1,L)
    L.append(n);
    GenerateBTree(n-1,L)

def GetNextPillar(pillar,direc):
    nextPillar = -1
    if direc == True:
        nextPillar = pillar + 1
        if nextPillar >= PillarCount:
            nextPillar = 0
    else:
        nextPillar = pillar - 1
        if nextPillar < 0:
            nextPillar = PillarCount - 1

    return nextPillar

if __name__ == '__main__':
    Hanoi(5)